2021-2022 BUAA XCPC Team Supplementary Training 01 ¶

排名	当场过题数	至今过题数	总题数
2/22	6	11	12

A¶

solved by TYB&JLK

题意¶

\(n\le5\times 10^5\)

题解¶

把三个数组的数放到一起排序，从左到右扫，枚举最大的数，看\(d\)的范围内另外两种数的个数即可。

\(O(n\log n)\)

C¶

upsolved by JLK

题意¶

一棵\(n\)个点的树，给定\(m\)条路径，要求出一个最小的点集，使得所有路径都能经过至少一个点集里的点。

\(1 \le n,m \le 10^5\)

题解¶

先考虑链上的问题。一种最优策略是，每次找最左的右端点，然后选择这个点，删去所有经过它的链，以此类推。

推广到树上，可以求出每条路径两端点的LCA，可以每次取深度最大的LCA。

用树剖+BIT即可维护。选点的时候在dfs序位置+1，然后选前面的路径的时候对路径求和即可判断有没有经过选中点。

\(O(nlog^2n)\)

D¶

solved by JLK

题意¶

有一个电梯，初始在0层，每次只能带顾客上到某个楼层后马上下来回到0层。开关门以及顾客进出的时间不计，移动一层需要1时间。现在有\(n\)个顾客，第\(i\)个顾客在\(t_i\)时刻到达电梯口，需要到\(a_i\)层。求把所有顾客都送到目标楼层并且电梯回到0层的最小时间。

\(1 \le n \le 2\times 10^5,1 \le t_i,a_i \le 10^9\)

题解¶

首先可以观察到，和决策有关的顾客只有以\(t_i\)为下标，\(a_i\)在递减单调栈里的顾客。因为假设在某个满足上述条件顾客\(a\)前有一个顾客\(b\)，满足\(t_b\le t_a,a_b \le a_a\)，那么不考虑\(b\)，在送\(a\)上去的时候顺路送\(b\)上去即可。

那么现在只考虑单调栈里的元素。下面讨论均在只剩下单调栈内元素的序列内。

还可以观察到，如果\(i\)顾客被送上楼了，那么\([1,i]\)区间内的顾客此时应该已经全部被送上楼了。因为若\(\exist j \lt i\)，\(j\)没有被送上楼，那么已经要在更后面送上楼，而后面的\(a_k\)更小，\(a_j-a_k\)更大，这样会导致电梯浪费更多只带\(j\)顾客，显然是不优的。

那么可以使用dp解决。

令\(dp_i\)为\([1,i]\)顾客都送上楼且电梯回到0层的最小时间。

容易列出转移方程：\(dp_i=\min\limits_{j=0}^{i-1}\{max\{dp_j,t_i\}+2\times a_{j+1} \}\)

可以分两类考虑：\(dp_j \le t_i\)和\(dp_j \gt t_i\)。

由于\(t_i\)递增，第一种情况已经有的元素不会改变，只会新加进来元素。而第二种情况会减少元素。对前者开一个变量维护最小值；后者用两个堆维护，一个存\(dp_j\)，一个存\(dp_j+2 \times a_{j+1}\)。每当移动\(t_i\)时，会出现\(dp_j\)从后者变成前者，这可以不断从堆里判断并取出元素，扔到第一种情况里。再开一个堆实现可删除堆即可。

答案即为\(dp_n\)。

\(O(nlogn)\)

E¶

upsolved by JLK

题意¶

给一个\(n\)个点\(m\)条边的有向无环图。要求在\(m\)条边里选出两组\(n-1\)条边，第一组边满足从\(a\)点出发能到达所有点，第二组边满足从所有点出发能到达\(b\)点。给出一种方案。

\(1 \le n\le 5\times 10^5,1 \le m \le 10^6\)

题解¶

很暴力的做法是二分图匹配：第一组边相当于除了\(a\)每个点入度为1，第二组边相当于除了\(b\)每个点出度为1。那么看做是一个二分图，左边是\(2n\)个点，右边\(m\)条边。左边\(n \(个点代表入度，另外\)n\)个点代表出度，这和边是一一对应的。首先对\(b\)出度连到\(a\)入度新建两条边，这样就只需要保证所有点都入度/出度为1即可。如果一条边放在第一组，就连到终点的入度，否则连到起点的出度。这样如果能跑出一个完美匹配，那么就可行。

但是这个二分图有很好的性质：右边的点一定度数为2。考虑二分图匹配时的增广路，实际上对于一个右边的点，连法是确定的，只和左边的选择有关。那么可以直接把这条边当做一条连接起点和终点的边。接下来考虑如何增广。实际上合法的增广路是若干个基环树。对于某个基环树，可以钦定环的顺序，使得增广路成立。

那么只要找到若干个基环树就行了。这可以通过dfs若干次解决。

\(O(n+m)\)

F¶

upsolved by TYB

题意¶

给出\(n\)个数，求删掉\(k\)个数后剩下数的\(\gcd\)最大值。

\(n\le10^5,k\le \frac{n}{2},a_i\le 10^{18}\)

题解¶

首先有个性质，每次随机选一个数，选了\(p\)个，那么这些数中全都不在最后的答案集合的概率为\(\frac{1}{2^p}\)，这启发我们可以把问题转化为一定选某个数，最后答案最大是多少，但这样也做不了。考虑这样一种做法：设当前我们已经得到的最优答案为\(ans\)，同样每次选一个数，我们不考虑求出包含它的最优答案，而是考虑将答案变得更优。若选了一个数后，\(\gcd\)会\(\le ans\)，我们就将其删去，看是否会删去超过\(k\)个数，不会则更新答案。这样做\(100\)轮就可以通过了。但我现在还不是特别会算这个概率，只能感性理解一下。

G¶

solved by YZW

题意¶

\(n\) 个 \([-10^9,10^9]\) 的变量 \(o_i\)，\(m\) 个形如 \(o_{a_i}+d_i\leq o_{b_i}+T\) 的限定条件，部分 \(o_i\) 值给出，求最小的 \(T\) 使得存在一组变量满足所有条件成立。

\(1\leq n\leq 1000\)，\(1\leq m\leq 2000\)，\(1\leq d_i\leq 100\)，\(1\leq o_i\leq 10^5\)。多组数据。

题解¶

移项即得：\(o_{b_i}+T-d_i\geq o_{a_i}\)，并且注意到对于 \(T_1>T_2\)，若 \(T_2\) 满足要求则 \(T_1\) 必然满足要求，故二分 \(T\) 根据不等关系构图跑差分约束系统即可。

时间复杂度 \(O(nm\log T)\)

H¶

upsolved by JLK

题意¶

交互题。有一棵\(n\)个点的树，可以进行询问，每次询问给出一个点集。

对于每次询问的点集，对整棵树进行如下操作：

1：依次去掉所有度为1且不在点集里的点。

2：依次去掉所有度为2且不在点集里的点。

交互器会返回树上剩下的点数。

求整棵树的形态（以1为根）。保证原树没有度为2的点。

\(1 \le n \le 100\)，询问次数小于2550。

题解¶

首先用\(n\)次询问，每次询问除了\(i\)以外的\(n-1\)个点，可以找出叶子结点。

然后所有点就分为了叶子结点和非叶子结点。观察2550，可以猜想是枚举一个叶子结点，一个非叶子结点。但询问两个点是没有意义的，还需要一个点。

那么尝试固定一个叶子结点为根（因为非叶子结点情况比较复杂）。然后枚举，询问三个点的点集，如果返回也为3，就说明非叶子结点是叶子结点的祖先。

这样枚举之后可以得到每个非叶子结点的子树里儿子个数，以及每个叶子结点的祖先。由于保证原树不存在度为2的点，叶子结点的祖先的儿子个数一定是随着深度减小而递增的。那么就可以确定叶子结点的祖先顺序了。连边之后再从1开始dfs，得到每个点的父亲即可。

这样的询问次数最大为\(100+49\times 50=2550\)，恰好是上界。

I¶

upsolved by TYB

题意¶

给出一个字符串\(S\)，\(q\)次询问，每次询问给出\(k\)个区间\([l_1,r_1]...[l_k,r_k]\)，求在\(S[l_1,r_1],S[l_2,r_2],...,S[l_k,r_k]\)这\(k\)个串中选出若干个，且任意两个选出来的串都不存在一个串是另一个串前缀的情况的方案数。

\(|S|\le4\times 10^5,\sum k\le4\times 10^5\)

题解¶

把原串反过来，前缀转化为后缀。建后缀自动机，考虑一次询问怎么做。对于每一个区间，倍增找到在后缀树上对应的节点并打标记，则问题转化为在后缀树上选若干个标记的节点，且选出来的节点不存在一个是另一个的祖先的方案数。这可以用简单的树形DP解决。注意到\(\sum k\)的限制，只要对每个询问建虚树就好了。

J¶

solved by JLK

题意¶

有长度为\(n\)的序列\(a_i\)，\(q\)次询问，每次询问\([l_i,r_i]\)内存在多少子序列，使得\(a_{i_1}+a_{i_2}+\cdots+a_{i_k}\mod m= 0\)。

\(1 \le n,q \le 2\times 10^5,1 \le m \le 20,0 \le a_i \le 10^9\)

题解¶

首先把所有\(a_i\)直接对\(m\)取模。答案可以看做\(r-l+1\)个长度为\(m\)的多项式的循环卷积在0处的取值。

这题主要的瓶颈在于，如果要合并两个循环卷积，复杂度为\(O(m^2)\)，而如果只是加入一个数，或者是合并两个循环卷积得到0位置的值，就只需要\(O(m)\)。

有一种分治方法可以避免前者，只用后者。

就是把每个询问挂在\(l\)和\(r\)上，分治的时候对每个区间求跨过中间点的方案数。

那么可以以中间点为中心，向两边分别做循环卷积。然后遍历询问，如果询问区间跨过了中间点，就可以合并两边的循环卷积计算。

注意要判断询问区间和当前区间的相对位置关系。以及不能出现全不选的情况。（这种情况在最后加上）

如果询问区间的另一个端点跨过了整个分治区间，那么可以出现询问端点所在半区间不选，但是另一个半区间一定要选。否则，两边都必须要选。

\(O((n+q)mlogn)\)

K¶

solved by TYB

题意¶

给出一个字符串\(S\)和若干字符串\(t_i\)，求每个\(t_i\)在\(S\)中的不重叠最大出现次数。

\(|S|,\sum|t_i|\le10^5\)

题解¶

根号分治。

长度大于根号的串不超过根号个，直接\(O(n)\)暴力匹配；

对于长度小于根号的串建\(Trie\)，对\(S\)的每个位置往后匹配根号个位置，若能匹配则检查与上次出现是否重叠。当然也可以写hash。

L¶

solved by YZW

题意¶

给出 \(n\) 个点 \(m\) 条边的无向图，\(1\) 号点与所有点联通，第 \(i\) 条边有边权 \(c_i\)。对于每条边，求其边权增加后，有多少个点到 \(1\) 号点的最短路径长度随之增加。

\(1\leq n\leq 2\times 10^5\)，\(n-1\leq m\leq 2\times 10^5\)，\(1\leq c_i\leq 10^9\)。

题解¶

建立最短路图（这学期我讨论课作业就提及了这玩意……），边上添加不计入子数大小的辅助点，求出其支配树，边对应点的子树大小即为该边答案。

记录¶

开场看题，过了好一会儿也没有人过题，在想DFJ三个题。

42min：JLK AC A

1h1min：JLK AC D

1h26min：TYB AC K（-1）

3h8min：YZW AC L

3h35min：JLK AC J

4h54min：YZW AC G

总结¶

TYB：样例较弱时出点小数据测一下；多学点东西，这次的查分约束忘了，支配树也不会。

JLK：这次只能说切题太慢了，F一直想不到卡了好久。应该要多换题想想。

Dirt¶

K（-1）：有个小地方写错了，应该交之前出点数据测一下。

L（-3）：LCA写错（-1），Dijkstra写错（-2）

J（-2）：一开始莽了个复杂度错的做法（-1），写正解时错了一次（-1）

G（-6）：精度问题，eps大了

2021-2022 BUAA XCPC Team Supplementary Training 01¶

A¶

题意¶

题解¶

B¶

题意¶

题解¶

C¶

题意¶

题解¶

D¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

H¶

题意¶

题解¶

I¶

题意¶

题解¶

J¶

题意¶

题解¶

K¶

题意¶

题解¶

L¶

题意¶

题解¶

记录¶

总结¶

Dirt¶

2021-2022 BUAA XCPC Team Supplementary Training 01 ¶